import java.util.List;
import java.util.Comparator;
import java.util.PriorityQueue;


/**
 * implements a data structure used for prim algorithm
 * @author BaoTam
 */
public class MyPrimStructure implements Structure {

	PriorityQueue<Path> queue;
	
	/**
	 * instantiate an empty MyPrimStructure with initial capacity 11
	 */
	public MyPrimStructure() {
		queue = new PriorityQueue<Path>(11, new PrimComparator<Path>());
	}
	
	/**
	 * add a path to the structure
	 * @param p, a path
	 */
	public void add(Path p) {
		queue.add(p);
	}

	@Override
	/**
	 * remove a path from the structure
	 * @return the removed path
	 */
	public Path remove() {
		return queue.remove();
	}

	@Override
	/**
	 * @return true if the structure is empty, false otherwise
	 */
	public boolean isEmpty() {
		return queue.isEmpty();
	}
	
	/**
	 * a comparator that is used when comparing two paths in the structure.
	 * @author BaoTam
	 *
	 * @param <T>
	 */
	private class PrimComparator<T extends Path> implements Comparator<T> {

		/**
		 * @param path1
		 * @param path2
		 * @return a positive number if path1 > path2, negative if path1 < path2, 0 if they are equal
		 */
		public int compare(T path1, T path2) {
			List<Pair> path1List = path1.getPath();
			List<Pair> path2List = path2.getPath();
			return path1List.get(path1List.size()-1).getWeight() - path2List.get(path2List.size()-1).getWeight();
		}
		
	}

}
